Assume the following rules are for the tic-tac-toe game on an n x n board between two players:
- A move is guaranteed to be valid and is placed on an empty block.
- Once a winning condition is reached, no more moves are allowed.
- A player who succeeds in placing
nof their marks in a horizontal, vertical, or diagonal row wins the game.
Implement the TicTacToe class:
TicTacToe(int n)Initializes the object the size of the boardn.int move(int row, int col, int player)Indicates that player with idplayerplays at the cell(row, col)of the board. The move is guaranteed to be a valid move.
Follow up:
Could you do better than O(n2) per move() operation?
Example 1:
Input ["TicTacToe", "move", "move", "move", "move", "move", "move", "move"] [[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]] Output [null, 0, 0, 0, 0, 0, 0, 1] Explanation TicTacToe ticTacToe = new TicTacToe(3); Assume that player 1 is "X" and player 2 is "O" in the board. ticTacToe.move(0, 0, 1); // return 0 (no one wins) |X| | | | | | | // Player 1 makes a move at (0, 0). | | | | ticTacToe.move(0, 2, 2); // return 0 (no one wins) |X| |O| | | | | // Player 2 makes a move at (0, 2). | | | | ticTacToe.move(2, 2, 1); // return 0 (no one wins) |X| |O| | | | | // Player 1 makes a move at (2, 2). | | |X| ticTacToe.move(1, 1, 2); // return 0 (no one wins) |X| |O| | |O| | // Player 2 makes a move at (1, 1). | | |X| ticTacToe.move(2, 0, 1); // return 0 (no one wins) |X| |O| | |O| | // Player 1 makes a move at (2, 0). |X| |X| ticTacToe.move(1, 0, 2); // return 0 (no one wins) |X| |O| |O|O| | // Player 2 makes a move at (1, 0). |X| |X| ticTacToe.move(2, 1, 1); // return 1 (player 1 wins) |X| |O| |O|O| | // Player 1 makes a move at (2, 1). |X|X|X|
Constraints:
2 <= n <= 100- player is
1or2. 0 <= row, col < n(row, col)are unique for each different call tomove.- At most
n2calls will be made tomove.
move() operation can be done in O(1)?Average Rating: 4.84 (25 votes)
Solution
Overview
Tic Tac Toe is one of the classic games most of us have played in our childhood. The game rules are pretty simple. There are 2 players that take turns marking a position on an n * n board. The first player that makes n marks horizontally, vertically, or diagonally, wins the game.
The brute force approach to solve this problem is to iterate over the entire board of size n * n and check if the current player has marked any row, column, diagonal or anti-diagonal.
This approach is exhaustive and requires O(n2) time for every move. Let's look at other more efficient approaches to solve the problem.
Approach 1: Optimized Brute Force
Intuition
The simplest and most intuitive approach is to check on every move if the current player has won. Each player makes a move by marking a cell on the board. The given cell is located at row row and column col. The 4 ways in which a player can win are as follows:
- Player has marked the entire row given by
row. - Player has marked the entire column given by
col. - Player has marked the diagonal beginning at the top left corner of the board and ending at the bottom right corner.
- Player has marked the anti-diagonal beginning at the top right corner of the board and ending at the bottom left corner.
The following figure illustrates the 4 winning conditions.
How do we identify which cells lie on the diagonal or anti-diagonal?
Every cell on the main diagonal has a unique property; the row index equals the column index. Similarly, for every cell on the anti-diagonal, the value of the column index is equal to
n - row - 1.
Every move, we will check if any of the above conditions are true. If yes, we declare the current player as the winner and finish the game.
Algorithm
-
For a given
n, initialize a 2-dimensional arrayboardof sizen * nwith the values of all elements set to0. -
Every move, mark the
rowandcolon theboardwith the current player's idplayer. -
Now, we will check the following conditions to see if the current player has won.
-
Check if all of the cells for the given
roware marked by the current player. To do so, we must iterate over all the columns ranging from index0ton - 1, keeping therowindex constant. -
Check if all of the positions for the given
colare marked by the current player. To do so, we must iterate over all the rows ranging from index0ton - 1, keeping thecolindex constant. -
Check if the main diagonal is completely marked by the current player.
From the above intuition, we know that for each cell on the main diagonal, the
rowandcolindices are equal. Thus, every cell on the diagonal can be given byboard[row][row]. -
Check if the anti-diagonal is completely marked by the current player.
From the above intuition for each cell in the anti-diagonal, the value of the
colindex is equal ton - row - 1. Thus, every cell in the anti-diagonal could be given byboard[row][n - row - 1].
-
-
If the current player wins the game, then return
player. Otherwise, return0indicating that no one has won the game.
Implementation
Complexity Analysis
-
Time Complexity: O(n), as for every move we are iterating over
ncells 4 times to check for each of the column, row, diagonal row, and anti-diagonal. This gives us time complexity of O(4⋅n) which is equivalent to O(n). -
Space Complexity: O(n2), as we are using 2-dimensional array
boardof sizen * n.
Approach 2: Optimised Approach
Intuition
Our goal is to find if a player has won by marking an entire row, column, diagonal, or anti diagonal cells. Can we find this in constant time without iterating over each of the horizontal, vertical, and diagonal rows on every move? Yes! Let's find out how.
Let's break the problem into 2 parts,
-
First, on every move, we must determine whether a player has marked all of the cells in a row or column. In other words, we could say that, if there are
nrows andncolumns on a board, the player must have marked a certain row or columnntimes.From the given conditions, we know that a move is always valid and placed on an empty cell. Hence, we can be certain that if a player has marked any row n times, they must have marked a different column each time.
-
Second, on every move, we must determine whether a player has marked all of the cells on the main diagonal or anti-diagonal. Irrespective of the size of the board, there can only be one diagonal and one anti-diagonal.
Also, there are always
ncells on the diagonal or anti-diagonal. Thus, to win by either of these, a player must have marked the cells on the diagonal or anti-diagonalntimes.
Let's understand how can we implement this approach.
Algorithm
From the above intuition, we understand that we must use a data structure to count how many times a player has marked a particular row, column, or diagonal.
-
To implement the first part, for each player, we will build an array
rowsof sizen, whererows[i]stores the number of times a player has marked a cell on the ith row. Likewise, for each player, we will also build an arraycolsof sizen.Winning Condition: The player will win if either
rows[i]orcols[j]is equal tonafter the player has marked the cell on the ith row and jth column.Let
player1Rowsandplayer1Colsbe therowsandcolsarray for player 1. Likewise, letplayer2Rowsandplayer2Colsbe therowsandcolsfor player 2. The following figure illustrates the process formove(0, 0, 1)andmove(0, 2, 2).
-
To implement the second part, we can use a similar idea as above. Since there is only one diagonal and one anti-diagonal, for each player, we only need 2 integer variables
diagonalandantiDiagonal. These variables will store how many times a cell has been marked on each of the diagonals.Winning Condition: After a player has marked a cell on a diagonal row, we check if the value of variable
diagonalfor that player is equal ton. Similarly, after a player has marked a cell on an anti-diagonal row, we check if the value of variableantiDiagonalfor that player is equal ton.Let
player1Diagonalandplayer1AntiDiagonalbe thediagonalandantiDiagonalvariables for player 1. Likewise, letplayer2Diagonalandplayer2AntiDiagonalbe thediagonalandantiDiagonalfor player 2. The following figure illustrates the process formove(1, 1, 1)andmove(2, 0, 2).
Question - Can we further optimize this algorithm?"
Yes, we can. Since there are only 2 players, when implementing part 1, we can use the same data structure to store the marked row and column values for both players.
One way to implement this is to increment the count when player 1 marks a cell and decrement the count when player 2 marks a cell. With this, we can say that, if the value of rows[i] is equal to n, player 1 has marked ith row n times. Similarly, if the value of rows[i] is equal to -n, then player 2 has marked the ith row n times.
Similar logic applies to the columns and diagonals.
The following animation illustrates the idea.
The algorithm can be implemented as follows:
-
For a given
n, initialize arraysrowsandcolsof sizenwith the value of every element set to0. -
For each move, we must increment/decrement the row, column, diagonal, and anti-diagonal according to who is the current player and which cell was marked. If the current player is player 1, we increment the value and if it is player 2, we decrement the value.
Note: If we apply simple math rules, we can increment or decrement the values irrespective of the player.
We can use an additional variable
currentPlayerwith the value1for player 1 and-1for player 2, and add the value ofcurrentPlayerto the current row, column, diagonal and anti-diagonal. -
As a final step, we must determine whether the current player has won the game. If any row, column, diagonal, or anti-diagonal is equal to
n(for player 1) or-n(for player 2) then the current player has won the game.Also, rather than having separate conditions to check whose turn it is, we can check the absolute values.
Implementation
Complexity Analysis
Let, n be the length of string s.
-
Time Complexity: O(1) because for every move, we mark a particular row, column, diagonal, and anti-diagonal in constant time.
-
Space Complexity: O(n) because we use arrays
rowsandcolsof sizen. The variablesdiagonalandantiDiagonaluse constant extra space.
Amazing solution. Approach 2 was literally an eye-opener.
It shows how the given constraints play equally important role in solving a problem. You were able to relax this problem using those constraints and solve it in constant time. Thanks for the article!
Well, my first idea is close to the 2nd approach except that I used 2 arrays of rows/cols/diags, each counts the number of moves made by each player, which took 2 times of space but is a little bit faster.
May 22, 2021 5:22 AM
In case someone interested in python3
class TicTacToe:
def __init__(self, n: int):
self.n=n
self.horiz=[0]*n
self.vert=[0]*n
self.diag1=0
self.diag2=0
def move(self, row: int, col: int, player: int) -> int:
n=self.n
move=1
if player == 2:
move=-1
self.horiz[col] += move
self.vert[row] += move
if row==col:
self.diag1 += move
if row+col == (n-1):
self.diag2 += move
if abs(self.horiz[col])==n or abs(self.vert[row])==n or abs(self.diag1)==n or abs(self.diag2)==n:
return player
return 0
I dont know if I thought of 2nd approach because the follow up said i could do better than O(n^2), or if that was the natural thing to do
May 24, 2021 3:38 AM
For the O(1) solution, my initial thought is using HashMap for rows and columns...
Using the two arrays in Approach2 is so clever which is a good trick to remember :)
The second approach is goddamn amazing. Thank you for brilliant explanation. :)
The 2nd approach is amazing! My brain won't come up with such a solution ever...
May 14, 2021 9:49 AM
This is an award winning article! Thank you for sharing the explanation!
This is truly an EXCELLENT article. Approach two blew my mind.
May 24, 2021 8:13 AM
The second solution is interesting but I question how practical it would be. Part of playing a game is seeing the board. You can't print out the current state of the board with the second solution, you only know if there is a winner.
You don't have any submissions yet.
xxxxxxxxxxclass TicTacToe {public: /** Initialize your data structure here. */ TicTacToe(int n) { } /** Player {player} makes a move at ({row}, {col}). @param row The row of the board. @param col The column of the board. @param player The player, can be either 1 or 2. @return The current winning condition, can be either: 0: No one wins. 1: Player 1 wins. 2: Player 2 wins. */ int move(int row, int col, int player) { }};/** * Your TicTacToe object will be instantiated and called as such: * TicTacToe* obj = new TicTacToe(n); * int param_1 = obj->move(row,col,player); */


